Polar codes, proposed by Arikan [1], are the first class of constructive coding schemes that are provable to achieve the symmetric capacity of the binary-input discrete memoryless channels under a low-complexity Successive Cancellation (SC) decoder. However, the finite-length performance of polar codes under SC is not competitive compared to other modern channel coding schemes such as Low-Density Parity-Check (LDPC) codes and turbo codes. Later, a SC List (SCL) decoder is proposed in [2], which can approach the performance of optimal Maximum-Likelihood (ML) decoder. By concatenating a simple Cyclic Redundancy Check (CRC) coding, it was shown that the performance of concatenated polar code is competitive with that of well-optimized LDPC and turbo codes. As a result, polar codes are being considered as a candidate for future Fifth Generation (5G) wireless communication systems.
The main idea of polar coding is to transform a pair of identical binary-input channels into two distinct channels of different qualities, one better and one worse than the original binary-input channel. By repeating such a pair-wise polarizing operation on a set of 2M independent uses of a binary-input channel, a set of 2M “bit-channels” of varying qualities can be obtained. Some of these bit channels are nearly perfect (i.e., error free) while the rest of the bit channels are nearly useless (i.e., totally noisy). The point is to use the nearly perfect channel to transmit data to the receiver while setting the input to the useless channels to have fixed or frozen values (e.g., 0) known to the receiver. For this reason, those input bits to the nearly useless and the nearly perfect channel are commonly referred to as frozen bits and non-frozen (or information) bits, respectively. Only the non-frozen bits are used to carry data in a polar code. An illustration of the structure of a length-8 polar code is illustrated in FIG. 1.
Although the original polar code, as proposed by Arikan [1], was proven to be capacity achieving with a low-complexity SC decoder, the finite-length performance of polar codes under SC is not competitive compared to other modern channel coding schemes such LDPC and turbo codes. A more complex decoder, namely the SCL decoder, is proposed in [2], where a list of more than one surviving decision path is maintained in the decoding process, but the resulting performance is still unsatisfactory. In [2], it was further proposed that by concatenating a linear outer code, namely a CRC code, with the original polar code as inner code, the outer code can be used to check if any of the candidate paths in the list are correctly decoded. Such a two-step decoding process significantly improves the performance and makes polar codes competitive with that of well-optimized LDPC and Turbo codes. However, such a two-step decoding process is in general sub-optimal as each step does not take into the account of the structure of the other (inner or outer) code.